//-------------------------------------------------------------------------------------------------
// Copyright (c) Bradford W. Mott and Flare Contributors
// North Carolina State University, Department of Computer Science
// The IntelliMedia Group
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
// SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
// OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//-------------------------------------------------------------------------------------------------

using System.Collections.Generic;
using UnityEngine;
using Poly2Tri;
using Flare.Geom;

namespace Flare.Display
{
    /// <summary>
    /// The Graphics class provides a drawing API for creating filled vector shapes. The
    /// Sprite and Shape classes support drawing using an instance of the Graphics class.
    /// </summary>
    public class Graphics
    {
        // Struct that pairs a fill style with a path
        private struct FilledPath
        {
            public object fill { get; private set; }
            public GraphicsPath path { get; private set; }

            public FilledPath(object fill, GraphicsPath path)
            {
                this.fill = fill;
                this.path = path;
            }
        }

        private object m_currentFill;
        private GraphicsPath m_currentPath;
        private Point m_currentLocation;
        private Point m_lastMoveToLocation;
        private LineStyle m_currentLine;

        private List<FilledPath> m_filledPaths;
        private Dictionary<object, List<LineSegment>> m_linePaths;

        private bool m_dirty;
        private List<Mesh> m_meshCache;
        private Dictionary<object, LineMesh> m_lineMeshCache;

        private Vector4 decodeConstant;

        private static Material line_material = new Material(Shader.Find("Flare/Line"));

        /// <summary>
        /// Returns true if the graphics object contains any filled paths or lines.
        /// </summary>
        internal bool ContainsPaths
        {
            get
            {
                return (m_filledPaths.Count != 0) || (m_linePaths.Count != 0);
            }
        }

        internal Graphics()
        {
            Clear();
        }

        internal Graphics(Graphics gr)
        {
            Clear();

            // NOTE: Since the GraphicsPath object in m_filledPaths are not accessible we'll
            // create a shallow copy of them to conserve resources
            this.m_filledPaths = new List<FilledPath>(gr.m_filledPaths);
            this.m_linePaths = new Dictionary<object, List<LineSegment>>(gr.m_linePaths);

            // Since we're creating a copy we can use any cached meshes as well
            this.m_meshCache = new List<Mesh>(gr.m_meshCache);
            this.m_lineMeshCache = new Dictionary<object, LineMesh>(gr.m_lineMeshCache);

            // Retain the dirty state of the original Graphics object
            this.m_dirty = gr.m_dirty;
        }

        /// <summary>
        /// Clears the vector shapes drawn to this graphics object.
        /// </summary>
        public void Clear()
        {
            m_dirty = false;
            m_currentFill = null;
            m_currentLine = null;
            m_currentPath = new GraphicsPath();
            m_currentLocation = new Point(0.0f, 0.0f);
            m_lastMoveToLocation = new Point(0.0f, 0.0f);

            decodeConstant = new Vector4(1.0f, 1.0f / 255.0f, 1.0f / 65025.0f, 1.0f / 160581375.0f);

            m_filledPaths = new List<FilledPath>();
            m_linePaths = new Dictionary<object, List<LineSegment>>();
            m_meshCache = new List<Mesh>();
            m_lineMeshCache = new Dictionary<object, LineMesh>();
        }

        /// <summary>
        /// Starts drawing a shape using the specified solid fill color.
        /// </summary>
        public void BeginFill(uint color)
        {
            BeginFill(new GraphicsSolidFill(color, 1.0f));
        }

        /// <summary>
        /// Starts drawing a shape using the specified solid fill color and alpha value.
        /// </summary>
        public void BeginFill(uint color, float alpha)
        {
            BeginFill(new GraphicsSolidFill(color, alpha));
        }

        /// <summary>
        /// Starts drawing a shape using a bitmap fill.
        /// </summary>
        public void BeginBitmapFill(BitmapData bitmapData, Matrix matrix = null,
            bool repeat = true, bool smooth = false)
        {
            BeginFill(new GraphicsBitmapFill(bitmapData, matrix, repeat, smooth));
        }

        internal void LineStyle(LineStyle style)
        {
            EndFill();
            m_currentLine = style;
        }

        internal void BeginFill(object fill)
        {
            if (m_currentLine == null)
            {
                EndFill();
            }
            m_currentFill = fill;
        }

        /// <summary>
        /// Ends drawing the filled shape.
        /// </summary>
        public void EndFill()
        {
            if (m_currentFill != null)
            {
                if (!m_lastMoveToLocation.Equals(m_currentLocation))
                {
                    LineTo(m_lastMoveToLocation.x, m_lastMoveToLocation.y);
                }
                m_filledPaths.Add(new FilledPath(m_currentFill, m_currentPath));

                // For now, we only need to mark dirty true once a new fill has been defined;
                // however, onces line styles are supported we'll need to make things dirty
                // whenever a new edge is added.
                m_dirty = true;
            }
            m_currentFill = null;
            m_currentLine = null;
            m_currentPath = new GraphicsPath();
        }

        internal struct LineSegment
        {
            public float width;
            public float radius;
            public Vector2 first;
            public Vector2 last;
            public Vector2 p0, p1, p2, p3;
            public Vector3 e0, e1, e2, e3;

            public LineSegment(float w, float r, Vector2 a, Vector2 b)
            {
                radius = r;
                width = w;
                first = a;
                last = b;

                if (radius < 1.0f) radius =1.0f;

                // Find the vertices of the rectangular box surrounding the line. Extend the box by r in
                // all directions to make sure all fragments get passed to the shader.
                Vector2 perpendicularOffset = new Vector2(last.y - first.y, first.x - last.x);
                perpendicularOffset.Normalize();
                perpendicularOffset = perpendicularOffset * (radius + width / 2);

                Vector2 parallelOffset = (last - first).normalized;
                parallelOffset = parallelOffset * (radius + width / 2);

                p0 = first + perpendicularOffset - parallelOffset;
                p1 = first - perpendicularOffset - parallelOffset;
                p2 = last - perpendicularOffset + parallelOffset;
                p3 = last + perpendicularOffset + parallelOffset;

                float filter_scale;
                if (width > 2.0f * radius)
                {
                    filter_scale = 1.0f / (2.0f * radius);
                }
                else
                {
                    filter_scale = 2.0f / (2.0f * radius + width);
                }

                float root = (p0.x - p3.x) * (p0.x - p3.x) + (p0.y - p3.y) * (p0.y - p3.y);
                root = 1.0f / Mathf.Sqrt(root);

                float root2 = (p3.x - p2.x) * (p3.x - p2.x) + (p3.y - p2.y) * (p3.y - p2.y);
                root2 = 1.0f / Mathf.Sqrt(root2);

                float k = filter_scale * root;
                float g = filter_scale * root2;

                //-----------------------------------------------------------------------

                e0 = new Vector3(k * (p0.y - p3.y), k * (p3.x - p0.x),
                    k * (p3.y * p0.x - p3.x * p0.y));

                e1 = new Vector3(g * (p1.y - p0.y), g * (p0.x - p1.x),
                    g * (p0.y * p1.x - p0.x * p1.y));

                e2 = new Vector3(k * (p2.y - p1.y), k * (p1.x - p2.x),
                    k * (p1.y * p2.x - p1.x * p2.y));

                e3 = new Vector3(g * (p3.y - p2.y), g * (p2.x - p3.x),
                    g * (p2.y * p3.x - p2.x * p3.y));
            }
        }

        internal struct LineMesh
        {
            public Mesh mesh;
            public Texture2D edgeCoeffs;
            public Vector4 decode;
            public int numSegs;
            public Vector4 delta;

            public LineMesh(Mesh m, Texture2D e, Vector4 de, int n, Vector4 d)
            {
                mesh = m;
                edgeCoeffs = e;
                decode = de;
                numSegs = n;
                delta = d;
            }
        }

        /// <summary>
        /// Add a curve from the current drawing position to the anchor point
        /// using the control point.
        /// </summary>
        public void CurveTo(float controlX, float controlY, float anchorX, float anchorY)
        {
            // if there is a linestyle active, make a new GraphicsPath for this command
            if (m_currentLine != null)
            {
                float width = m_currentLine.width;
                float radius = m_currentLine.radius;
                List<LineSegment> lp;

                // Dissect the curve into a series of straight lines
                Point p0 = new Point(m_currentLocation.x, m_currentLocation.y);
                Point p1 = new Point(controlX, controlY);
                Point p2 = new Point(anchorX, anchorY);
                List<PolygonPoint> points = DissectCurve(p0, p1, p2);

                // Add each of the straight lines to the path
                Vector2 current = new Vector2(m_currentLocation.x, m_currentLocation.y);
                foreach (PolygonPoint p in points)
                {
                    Vector2 next = new Vector2((float)p.X, (float)p.Y);

                    LineSegment newLS = new LineSegment(width, radius, current, next);

                    if (m_linePaths.TryGetValue(m_currentLine, out lp))
                    {
                        lp.Add(newLS);
                    }
                    else
                    {
                        lp = new List<LineSegment>();
                        lp.Add(newLS);
                        m_linePaths.Add(m_currentLine, lp);
                    }
                    current.x = (float)p.X;
                    current.y = (float)p.Y;
                }
            }
            if (m_currentFill != null)
            {
                m_currentPath.CurveTo(controlX, controlY, anchorX, anchorY);
            }

            m_currentLocation = new Point(anchorX, anchorY);
        }

        /// <summary>
        /// Add a line from the current drawing position to the specified point.
        /// </summary>
        public void LineTo(float x, float y)
        {
            // if there is a linestyle active, make a new GraphicsPath for this command
            if (m_currentLine != null)
            {
                List<LineSegment> lp;
                Vector2 current = new Vector2(m_currentLocation.x, m_currentLocation.y);
                Vector2 next = new Vector2(x, y);
                float width = m_currentLine.width;
                float radius = m_currentLine.radius;

                LineSegment newLS = new LineSegment(width, radius, current, next);

                if (m_linePaths.TryGetValue(m_currentLine, out lp))
                {
                    lp.Add(newLS);
                }
                else
                {
                    lp = new List<LineSegment>();
                    lp.Add(newLS);
                    m_linePaths.Add(m_currentLine, lp);
                }
                m_dirty = true;
            }
            if (m_currentFill != null)
            {
                m_currentPath.LineTo(x, y);
            }
            m_currentLocation = new Point(x, y);
        }

        /// <summary>
        /// Moves the current drawing position to the specified point.
        /// </summary>
        public void MoveTo(float x, float y)
        {
            if (m_currentFill != null)
            {
                m_currentPath.MoveTo(x, y);
            }
            m_currentLocation = new Point(x, y);
            m_lastMoveToLocation = new Point(x, y);
        }

        internal List<PolygonPoint> DissectCurve(Point p0, Point p1, Point p2)
        {
            List<PolygonPoint> points = new List<PolygonPoint>();
            // TODO bwmott 2013-01-19: Consider making the step size a property
            // on the loader or somewhere that could be set before loading a SWF.

            // Step along the curve based upon the distance from the anchor points.
            // The size of the steps will be so that the error is within 2.0 units.
            float d = (p2.Subtract(p0)).length;
            float step = 1.0f / (d / 2.0f);

            for (float t = step; t <= 1.0f - step; t = t + step)
            {
                float x = (Mathf.Pow(1.0f - t, 2.0f) * p0.x) +
                    (2.0f * (1.0f - t) * t * p1.x) +
                    (t * t * p2.x);
                float y = (Mathf.Pow(1.0f - t, 2.0f) * p0.y) +
                    (2.0f * (1.0f - t) * t * p1.y) +
                    (t * t * p2.y);
                points.Add(new PolygonPoint(x, y));
            }
            points.Add(new PolygonPoint(p2.x, p2.y));

            return points;
        }

        /// <summary>
        /// Copy the shapes drawn in the given graphics object into this graphics object.
        /// </summary>
        public void CopyFrom(Graphics gr)
        {
            Clear();

            // NOTE: Since the GraphicsPath object in m_filledPaths are not accessible we'll
            // create a shallow copy of them to conserve resources
            this.m_filledPaths = new List<FilledPath>(gr.m_filledPaths);
            this.m_linePaths = new Dictionary<object, List<LineSegment>>(gr.m_linePaths);

            // Since we're creating a copy we can use any cached meshes as well
            this.m_meshCache = new List<Mesh>(gr.m_meshCache);
            this.m_lineMeshCache = new Dictionary<object, LineMesh>();

            // Retain the dirty state of the original Graphics object
            this.m_dirty = gr.m_dirty;
        }

        internal void CacheMeshes()
        {
            if (!this.m_dirty)
            {
                return;
            }

            m_meshCache = new List<Mesh>();
            m_lineMeshCache = new Dictionary<object, LineMesh>();

            for (int i = 0; i < this.m_filledPaths.Count; ++i)
            {
                m_meshCache.Add(GenerateMesh(this.m_filledPaths[i].path));
            }
            foreach (var style in m_linePaths)
            {
                LineMesh mesh = GenerateLineMesh(style.Value);
                m_lineMeshCache[style.Key] = mesh;
            }

            this.m_dirty = false;
        }

        //--------------- Line Processing Methods ----------------------------------------
        private void LineSetup(LineMesh mesh)
        {
            line_material.SetTexture ("_edgeCoeffs", mesh.edgeCoeffs);
            line_material.SetVector ("_decode", mesh.decode);
            line_material.SetVector("_delta", mesh.delta);
        }

        private static void db(Vector2 v, string name)
        {
            Debug.Log(name + ": " + v.ToString ());
        }

        private static void db4(Vector4 v, string name)
        {
            Debug.Log(name + ": " + v.x + ", " + v.y + ", " + v.z + ", " + v.w);
        }

        //--------------------------------------------------------------------------------

        internal bool HitTest(Point local, bool shapeFlag)
        {
            // Ensure meshes are up-to-date
            CacheMeshes();

            if (shapeFlag)
            {
                for (int i = 0; i < this.m_meshCache.Count; ++i)
                {
                    Mesh mesh = this.m_meshCache[i];

                    // First, we check to see if it's within the bounds of the mesh
                    if (mesh.bounds.Contains(new Vector3(local.x, local.y, 0.0f)))
                    {
                        // Now, check each triangle in the mesh
                        if (PointInMesh(local, mesh))
                        {
                            return true;
                        }
                    }
                }
                // Do the same for line meshes
                foreach (var style in m_lineMeshCache.Values)
                {
                    if (style.mesh.bounds.Contains(new Vector3(local.x, local.y, 0.0f)))
                    {
                        if (PointInMesh(local, style.mesh))
                        {
                            return true;
                        }
                    }
                }

                return false;
            }
            else
            {
                Bounds? bounds = null;
                for (int i = 0; i < this.m_meshCache.Count; ++i)
                {
                    Mesh mesh = this.m_meshCache[i];

                    if (!bounds.HasValue)
                    {
                        bounds = mesh.bounds;
                    }
                    else
                    {
                        bounds.Value.Encapsulate(mesh.bounds);
                    }
                }
                // Again, repeat for line meshes
                foreach (var style in m_lineMeshCache.Values)
                {
                    if (!bounds.HasValue)
                    {
                        bounds = style.mesh.bounds;
                    }
                    else
                    {
                        bounds.Value.Encapsulate(style.mesh.bounds);
                    }
                }

                if (bounds.HasValue)
                {
                    return bounds.Value.Contains(new Vector3(local.x, local.y, 0.0f));
                }
                else
                {
                    return false;
                }
            }
        }

        private static bool PointInMesh(Point point, Mesh msh)
        {
            // See http://www.blackpawn.com/texts/pointinpoly/ for algorithim details

            int[] triangles = msh.triangles;
            Vector3[] vertices = msh.vertices;

            Vector3 p = new Vector3(point.x, point.y, 0.0f);

            for (int i = 0; i < triangles.Length; i += 3)
            {
                Vector3 a = vertices[triangles[i]];
                Vector3 b = vertices[triangles[i + 1]];
                Vector3 c = vertices[triangles[i + 2]];

                Vector3 cp1 = Vector3.Cross(c - b, p - b);
                Vector3 cp2 = Vector3.Cross(c - b, a - b);

                Vector3 cp3 = Vector3.Cross(b - a, p - a);
                Vector3 cp4 = Vector3.Cross(b - a, c - a);

                Vector3 cp5 = Vector3.Cross(c - a, p - a);
                Vector3 cp6 = Vector3.Cross(c - a, b - a);

                if ((Vector3.Dot(cp1, cp2) >= 0.0f) &&
                    (Vector3.Dot(cp3, cp4) >= 0.0f) &&
                    (Vector3.Dot(cp5, cp6) >= 0.0f))
                {
                    return true;
                }
            }

            return false;
        }

        //--------------------------------------------------------------------------------

        /// <summary>
        /// Check to see if a point is inside a polygon. This function was adpated from the
        /// article by Darel Rex Finley at http://alienryderflex.com/polygon/.
        /// </summary>
        /// <returns>true if the point is inside the polygon</returns>
        private static bool PointInPolygon(TriangulationPoint p,
            IList<TriangulationPoint> poly)
        {
            int j = poly.Count - 1;
            bool odd = false;

            for (int i = 0; i < poly.Count; ++i)
            {
                if ((poly[i].Y < p.Y && poly[j].Y >= p.Y) ||
                    (poly[j].Y < p.Y && poly[i].Y >= p.Y))
                {
                    if (poly[i].X + (p.Y - poly[i].Y) / (poly[j].Y - poly[i].Y) *
                        (poly[j].X - poly[i].X) < p.X)
                    {
                        odd = !odd;
                    }
                }
                j = i;
            }

            return odd;
        }

        /// <summary>
        /// Simple test to see if one polygon is enclosed within an outer polygon. This is not a
        /// general solution to enclosement. It only checks to see if the first point in the
        /// enclosed polygon is inside the outer polygon. Given the types of polygons generated
        /// by the Flash authoring system, this should work and be a sufficent solution.
        /// </summary>
        /// <returns>
        /// True if the enclosed polygon is within the encloser polygon.
        /// </returns>
        private static bool SimplePolygonEnclosedTest(Polygon enclosed, Polygon outer)
        {
            // TODO bwmott 2013-01-19: Consider adding a general purpose enclosement test so that
            // general programmatic shapes can be supported in the future.
            return PointInPolygon(enclosed.Points[0], outer.Points);
        }

        /// <summary>
        /// PolygonHierarchy class allows us to create a hierarchy of polygons enclosed within
        /// other polygons. The even levels of the hierarchy (starting at level 0) are solid
        /// polygons while the odd levels of the hierarchy are holes within their parent.
        /// </summary>
        private class PolygonHierarchy
        {
            public Polygon Polygon;
            public List<PolygonHierarchy> Children;

            public PolygonHierarchy(Polygon polygon, List<PolygonHierarchy> children = null)
            {
                Polygon = polygon;
                Children = (children == null) ? new List<PolygonHierarchy>() : children;
            }
        }

        /// <summary>
        /// Insert a new polygon within the polygon hierarchy based on which polygons enclose
        /// it, or which polygons it encloses.
        /// </summary>
        private static void InsertPolygonIntoHierarchy(ref List<PolygonHierarchy> root,
            Polygon polygon)
        {
            if (root == null)
            {
                root = new List<PolygonHierarchy>();
            }

            // See if any of the polygons in root are children of the polygon
            List<PolygonHierarchy> children = new List<PolygonHierarchy>();
            foreach (var ph in root)
            {
                if (SimplePolygonEnclosedTest(ph.Polygon, polygon))
                {
                    children.Add(ph);
                }
            }

            // If any of the polygons in root are children of the polygon then we've found
            // where we need to insert the polygon
            if (children.Count > 0)
            {
                // Remove children from root
                foreach (var ph in children)
                {
                    root.Remove(ph);
                }

                // Add polygon with it's children to the hierarchy
                root.Add(new PolygonHierarchy(polygon, children));
            }
            else
            {
                // Check to see if one of the polygons in root is an ancestor of the polygon
                foreach (var ph in root)
                {
                    if (SimplePolygonEnclosedTest(polygon, ph.Polygon))
                    {
                        // Found ancestor of the polygon so now add the polygon recursively to it
                        InsertPolygonIntoHierarchy(ref ph.Children, polygon);
                        return;
                    }
                }

                // No children or ancetor at this level so we'll just add the polygon
                root.Add(new PolygonHierarchy(polygon));
            }
        }

        /// <summary>
        /// Given hierarchy of polygons, populate the list of triangles using Poly2Tri.
        /// </summary>
        static void TriangulatePolygonHierarchy(List<PolygonHierarchy> root,
            List<Vector3> triangles)
        {
            foreach (var ph in root)
            {
                // Triangulate polygon after adding holes
                Polygon polygon = ph.Polygon;
                foreach (var hole in ph.Children)
                {
                    polygon.AddHole(hole.Polygon);
                }

                try
                {
                    P2T.Triangulate(polygon);
                }
                catch (global::System.Exception e)
                {
                    Log.Error(Subsystem.Playback, e, "Poly2Tri failed to triangulate polygon. "
                        + "Try reducing the complexity of the shape.");

                    /*
                    Log.WriteLine(Subsystem.LoadingGeneral,"Check: " + ph.Polygon.CheckPolygon());
                    Dictionary<Vector3, int> indexMap = new Dictionary<Vector3, int>();

                    string svg = "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">" +
                        "    <polygon points=\"";

                    for (int i = 0; i < ph.Polygon.Count; ++i)
                    {
                        Vector3 v = new Vector3(ph.Polygon[i].Xf, ph.Polygon[i].Yf, 0.0f);
                        svg += v.x + "," + v.y + " ";

                        if (indexMap.ContainsKey(v))
                        {
                            Log.WriteLine(Subsystem.LoadingGeneral,"Duplicate: " + ph.Polygon[i]);
                        }
                        else
                        {
                            indexMap.Add(v, 1);
                        }
                    }
                    svg += "\"" + "  style=\"fill:lime;stroke:purple;stroke-width:1\"/>" +
                        "</svg>";
                    Log.WriteLine(Subsystem.LoadingGeneral,svg);
                    Log.WriteLine(Subsystem.LoadingGeneral,e.ToString());
                    */
                }

                foreach (var tri in polygon.Triangles)
                {
                    triangles.Add(new Vector3(tri.Points[0].Xf, tri.Points[0].Yf, 0.0f));
                    triangles.Add(new Vector3(tri.Points[1].Xf, tri.Points[1].Yf, 0.0f));
                    triangles.Add(new Vector3(tri.Points[2].Xf, tri.Points[2].Yf, 0.0f));
                }

                // Handle adding triangles for children of the holes
                foreach (var child in ph.Children)
                {
                    TriangulatePolygonHierarchy(child.Children, triangles);
                }
            }
        }

        private static string DebugPrint(List<PolygonHierarchy> root, int level = 0)
        {
            string indent = "";
            for(int i = 0; i < level; ++i)
                indent += " ";

            string result = "";
            foreach (var p in root)
            {
                result += indent + p.Polygon.Points.Count + "\n";
                result += DebugPrint(p.Children, level + 8);
            }

            return result;
        }

        // Used for normalizing floats before encoding in RGBA
        internal static Vector2 GetMaxMinParameters (List<LineSegment> paths)
        {
            float max = float.NegativeInfinity;
            float min = float.PositiveInfinity;

            foreach (LineSegment lp in paths)
            {
                Vector4[] es = new Vector4[] { lp.e0, lp.e1, lp.e2, lp.e3};
                foreach (Vector4 e in es)
                {
                    if (e.x > max)
                    {
                        max = e.x;
                    } else if (e.x < min)
                    {
                        min = e.x;
                    }
                    if (e.y > max)
                    {
                        max = e.y;
                    } else if (e.y < min)
                    {
                        min = e.y;
                    }
                    if (e.z > max)
                    {
                        max = e.z;
                    } else if (e.x < min)
                    {
                        min = e.z;
                    }
                }
            }
            return new Vector2(min, max + 1);
        }

        internal static Color EncodeFloatRGBA(float v, float min, float max)
        {
            Vector4 enc;
            v = (v - min) / (max - min);
            enc = new Vector4(Frac(1.0f * v), Frac(255.0f * v), Frac(65025.0f * v),
               Frac(16581375.0f * v));
            Vector4 sub = new Vector4(enc.y / 255.0f, enc.z / 255.0f, enc.w / 255.0f, 0);
            enc = enc - sub;

            return new Color(enc.x, enc.y, enc.z, enc.w);
        }

        internal static float Frac(float v)
        {
            decimal d = (decimal)v;
            return (float)(d - decimal.Truncate(d));
        }

        internal LineMesh GenerateLineMesh (List<LineSegment> paths)
        {
            //---------------------- Create the mesh ---------------------//
            Texture2D edgeCoeffs = new Texture2D(paths.Count, 12, TextureFormat.ARGB32, false);
            edgeCoeffs.filterMode = FilterMode.Point;
            List<Vector3> vertices = new List<Vector3>();
            List<int> indices = new List<int>();
            List<Vector2> uv2s = new List<Vector2>();

            Vector2 parms = GetMaxMinParameters(paths);
            float min = parms.x;
            float max = parms.y;

            int k = 0;
            foreach (LineSegment lp in paths)
            {
                // The rectangle surrounding the line is calculated in the constructor for LineSegment.
                // Since the polygon is a rectangle, its triangulation is trivial and can be
                // determined immediately. Repeated vertices are necessary to pass per-triangle
                // information through the shader
                vertices.Add(new Vector3(lp.p0.x, lp.p0.y, 0.0f));
                vertices.Add(new Vector3(lp.p1.x, lp.p1.y, 0.0f));
                vertices.Add(new Vector3(lp.p2.x, lp.p2.y, 0.0f));
                vertices.Add(new Vector3(lp.p2.x, lp.p2.y, 0.0f));
                vertices.Add(new Vector3(lp.p3.x, lp.p3.y, 0.0f));
                vertices.Add(new Vector3(lp.p0.x, lp.p0.y, 0.0f));

                // The vertex and index buffers are also trivial
                int x = k * 6;
                int[] index = new int[6] {x + 0, x + 1, x + 2, x + 3, x + 4, x + 5};
                indices.AddRange(index);

                // Create the texture of edge coefficients
                int i = 0;
                Vector4[] eC = new Vector4[] {lp.e0, lp.e1, lp.e2, lp.e3};
                for (int j = 0; j < 4; j++)
                {
                    edgeCoeffs.SetPixel(k, i, EncodeFloatRGBA(eC[j].x, min, max));
                    edgeCoeffs.SetPixel(k, i + 1, EncodeFloatRGBA(eC[j].y, min, max));
                    edgeCoeffs.SetPixel(k, i + 2, EncodeFloatRGBA(eC[j].z, min, max));
                    i += 3;
                }

                edgeCoeffs.Apply ();

                // Finally, put the segment index into the uv channel for each of the segment's associated
                // vertices
                Vector2[] u = new Vector2[6];
                for (int j = 0; j < 6; j ++)
                {
                    u[j] = new Vector2((float)k, 0);
                }
                uv2s.AddRange(u);

                k++;
            }

            Vector4 decode = new Vector4(min, max - min, 0.0f, 0.0f);

            float texel_width = 1.0f / paths.Count;
            float texel_height = 1.0f / 12.0f;
            Vector4 delta = new Vector4(texel_width, texel_width / 2.0f, texel_height,
                texel_height / 2.0f);

            // Create the mesh
            Mesh msh = new Mesh();
            msh.vertices = vertices.ToArray();
            msh.triangles = indices.ToArray();
            msh.uv2 = uv2s.ToArray();

            LineMesh lm = new LineMesh(msh, edgeCoeffs, decode, paths.Count, delta);
            return lm;
        }

        /// <summary>
        /// Generate a Mesh from the given GraphicsPath.
        /// </summary>
        internal Mesh GenerateMesh(GraphicsPath path)
        {
            if (path.commands == null)
            {
                return null;
            }

            // TODO bwmott 2013-02-16: Consider changing GenerateMesh so that all of the paths
            // are submitted and a single Mesh is created using submeshes for the different
            // fill styles. This should be more efficient than having a Mesh per fill style.
            List<Polygon> polygons = new List<Polygon>();
            List<PolygonPoint> points = new List<PolygonPoint>();

            int index = 0;
            PolygonPoint startingPoint = new PolygonPoint(0.0, 0.0);

            foreach (var command in path.commands)
            {
                if (startingPoint != null)
                {
                    points = new List<PolygonPoint>();
                    if (command == GraphicsPathCommand.MOVE_TO)
                    {
                        points.Add(new PolygonPoint(path.data[index++], path.data[index++]));
                    }
                    else
                    {
                        points.Add(startingPoint);
                    }
                    startingPoint = null;
                }

                if (command != GraphicsPathCommand.MOVE_TO)
                {
                    if (command == GraphicsPathCommand.LINE_TO)
                    {
                        points.Add(new PolygonPoint(path.data[index++], path.data[index++]));
                    }
                    else if (command == GraphicsPathCommand.CURVE_TO)
                    {
                        Point p0 = new Point(points[points.Count - 1].Xf,
                            points[points.Count - 1].Yf);
                        Point p1 = new Point(path.data[index++], path.data[index++]);
                        Point p2 = new Point(path.data[index++], path.data[index++]);

                        // TODO bwmott 2013-01-19: Consider making the step size a property
                        // on the loader or somewhere that could be set before loading a SWF.

                        // Step along the curve based upon the distance from the anchor points.
                        // The size of the steps will be so that the error is within 2.0 units.
                        float d = (p2.Subtract(p0)).length;
                        float step = 1.0f / (d / 2.0f);

                        for (float t = step; t <= 1.0f - step; t = t + step)
                        {
                            float x = (Mathf.Pow(1.0f - t, 2.0f) * p0.x) +
                                (2.0f * (1.0f - t) * t * p1.x) +
                                (t * t * p2.x);
                            float y = (Mathf.Pow(1.0f - t, 2.0f) * p0.y) +
                                (2.0f * (1.0f - t) * t * p1.y) +
                                (t * t * p2.y);
                            points.Add(new PolygonPoint(x, y));
                        }
                        points.Add(new PolygonPoint(p2.x, p2.y));
                    }

                    PolygonPoint lastPoint = points[points.Count - 1];
                    if (points[0].Equals(lastPoint))
                    {
                        if (points.Count >= 3)
                        {
                            polygons.Add(new Polygon(points));
                        }
                        startingPoint = new PolygonPoint(lastPoint.X, lastPoint.Y);
                    }
                }
            }

            // Now that we have all of the closed polygons for this path let's create a
            // hierarchy of the polygons so we can identify solid polygons and hole polygons
            List<PolygonHierarchy> hierarchy = null;
            foreach (Polygon p in polygons)
            {
                InsertPolygonIntoHierarchy(ref hierarchy, p);
            }

            // Generate triangles from the polygon hierarchy
            List<Vector3> triangles = new List<Vector3>();
            TriangulatePolygonHierarchy(hierarchy, triangles);

            // Create vertex and index buffer from the triangles
            HashSet<Vector3> vertexSet = new HashSet<Vector3>();
            foreach (var vertex in triangles)
            {
                vertexSet.Add(vertex);
            }

            Vector3[] vertices = new Vector3[vertexSet.Count];
            Dictionary<Vector3, int> indexMap = new Dictionary<Vector3, int>();
            int vertexIndex = 0;
            foreach (var vertex in vertexSet)
            {
                indexMap.Add(vertex, vertexIndex);
                vertices[vertexIndex] = vertex;
                ++vertexIndex;
            }

            int[] indices = new int[triangles.Count];
            for (int i = 0; i < triangles.Count; ++i)
            {
                indices[i] = indexMap[triangles[i]];
            }

            // Create the mesh
            Mesh msh = new Mesh();
            msh.vertices = vertices;
            msh.triangles = indices;

            return msh;
        }

        //--------------------------------------------------------------------------------

        private static Material ms_solidMaterial = null;
        private static Material ms_bitmapMaterial = null;
        private static Material ms_gradientMaterial = null;

        internal void Render(Matrix mat, ColorTransform cxform)
        {
            CacheMeshes();

            // Create rendering materials if they haven't been created
            if (ms_solidMaterial == null)
            {
                Shader solidShader = Shader.Find("Flare/SolidFill");
                Shader bitmapShader = Shader.Find("Flare/BitmapFill");
                Shader gradientShader = Shader.Find("Flare/GradientFill");

                try
                {
                    ms_solidMaterial = new Material(solidShader);
                    ms_bitmapMaterial = new Material(bitmapShader);
                    ms_gradientMaterial = new Material(gradientShader);
                }
                catch
                {
                    Log.Error(Subsystem.Playback,
                        "Could not find '{0}' shader. Please ensure it is in a Resource folder.",
                        (solidShader == null) ? "Flare/SolidFill" :
                        ((bitmapShader == null) ? "Flare/BitmapFill" : "Flare/GradientFill"));
                }
            }

            for (int i = 0; i < this.m_filledPaths.Count; ++i)
            {
                object fill = this.m_filledPaths[i].fill;
                Mesh msh = this.m_meshCache[i];
                if (msh == null)
                {
                    continue;
                }

                if (fill is GraphicsSolidFill)
                {
                    GraphicsSolidFill solidFill = (GraphicsSolidFill)fill;
                    ms_solidMaterial.color = cxform.ApplyToColor(solidFill.color, solidFill.alpha);

                    if (ms_solidMaterial.SetPass(0))
                    {
                        UnityEngine.Graphics.DrawMeshNow(msh, (Matrix4x4)mat);
                    }
                }
                else if (fill is GraphicsBitmapFill)
                {
                    GraphicsBitmapFill bitmapFill = (GraphicsBitmapFill)fill;
                    ms_bitmapMaterial.color = cxform.ApplyToColor(0x00ffffff, 1.0f);
                    ms_bitmapMaterial.mainTexture = bitmapFill.bitmapData.texture;

                    float width = ms_bitmapMaterial.mainTexture.width;
                    float height = ms_bitmapMaterial.mainTexture.height;

                    ms_bitmapMaterial.mainTexture.wrapMode = bitmapFill.repeat ?
                        TextureWrapMode.Repeat : TextureWrapMode.Clamp;

                    Matrix4x4 m = Matrix4x4.TRS(new Vector3(0.0f, 1.0f, 0.0f), Quaternion.identity,
                        new Vector3(1.0f / width, -1.0f / height, 1.0f)) *
                        ((bitmapFill.matrix == null) ? Matrix4x4.identity :
                            (Matrix4x4)(bitmapFill.matrix));
                    ms_bitmapMaterial.SetMatrix("_TextureMatrix", m);

                    if (ms_bitmapMaterial.SetPass(0))
                    {
                        UnityEngine.Graphics.DrawMeshNow(msh, (Matrix4x4)mat);
                    }
                }
                else if (fill is GraphicsGradientFill)
                {
                    GraphicsGradientFill gradientFill = (GraphicsGradientFill)fill;
                    Matrix4x4 gm = (Matrix4x4)(gradientFill.matrix);

                    ms_gradientMaterial.color = cxform.ApplyToColor(0x00ffffff, 1.0f);
                    ms_gradientMaterial.mainTexture = gradientFill.texture;
                    ms_gradientMaterial.SetMatrix("_GradientMatrix", gm.inverse);
                    ms_gradientMaterial.SetFloat("_FocalPointRatio",
                        Mathf.Clamp(gradientFill.focalPointRatio, -1.0f, 1.0f));

                    // Select the correct shader pass based on the type of gradient
                    int pass;
                    if (gradientFill.type.Equals(GradientType.LINEAR))
                    {
                        if (gradientFill.spreadMethod.Equals(SpreadMethod.REFLECT))
                            pass = 1;
                        else if (gradientFill.spreadMethod.Equals(SpreadMethod.REPEAT))
                            pass = 2;
                        else
                            pass = 0;
                    }
                    else
                    {
                        if (gradientFill.spreadMethod.Equals(SpreadMethod.REFLECT))
                            pass = 4;
                        else if (gradientFill.spreadMethod.Equals(SpreadMethod.REPEAT))
                            pass = 5;
                        else
                            pass = 3;
                    }

                    if (ms_gradientMaterial.SetPass(pass))
                    {
                        UnityEngine.Graphics.DrawMeshNow(msh, (Matrix4x4)mat);
                    }
                }
            }
            
            if (this.m_linePaths.Count > 0)
            {
                foreach (var style in m_linePaths)
                {
                    object lineStyle = style.Key;
                    LineStyle lineFill = (LineStyle)lineStyle;

                    line_material.SetColor("_Color", cxform.ApplyToARGB(lineFill.color));
                    line_material.SetVector("_constant", decodeConstant);

                    LineMesh lm = m_lineMeshCache[lineStyle];

                    line_material.SetTexture("_MainTex", lineFill.filter);
                    this.LineSetup(lm);

                    if (line_material.SetPass(0))
                    {
                        UnityEngine.Graphics.DrawMeshNow(lm.mesh, (Matrix4x4)mat);
                    }
                }
            }
        }
        
        internal void RenderAsMask(Matrix mat)
        {
            CacheMeshes();

            // Mask rendering only includes filled paths
            for (int i = 0; i < this.m_filledPaths.Count; ++i)
            {
                Mesh msh = this.m_meshCache[i];
                if (msh == null)
                {
                    continue;
                }
                
                UnityEngine.Graphics.DrawMeshNow(msh, (Matrix4x4)mat);
            }
        }
    }
}
